#include <stdio.h>
#include <stdlib.h>
// 非循环双链表 访问频度域 freq 初值为0
// 每进行一次Locate(L,x) 令元素值为x的结点中的freq域增加1
// 保证链表中的结点按照访问频度递减排序
// 频度相同时最近访问的结点在前
// 编写Locate(L, x)

typedef struct DLNode
{
    int data;
    int freq;
    DLNode *pred, *next;
}*DLinkedList, DLNode;

void swap(DLNode *L1, DLNode *L2) {
	int temp = L1->data;
	L1->data = L2->data;
	L2->data = temp;

	temp = L1->freq;
	L1->freq = L2->freq;
	L2->freq = temp;
}

bool Locate(DLinkedList &L, int x){
    // 找到x
    DLNode *ptr = L->next;
    while (ptr)
    {
        if (ptr->data == x)
            break;
		ptr = ptr->next;		        
    }
	if (ptr == NULL)
		return false;
	DLNode *now = ptr;

	// 阈增1
	now->freq++;
	// 向前移动到合适位置
	// 找到节点符合位置
	while (now->freq >= ptr->pred->freq && ptr->pred != L) {
		ptr = ptr->pred;
	}
	// 替换
	swap(ptr,now);
	return true;
}

// 测试函数
DLNode * NewDLNode(int e) {
	DLNode *r = (DLNode*)malloc(sizeof(DLNode));
	r->next = NULL;
	r->pred = NULL;
	r->data = e;
	r->freq = 0;
	return r;
}

void InsertNode(DLinkedList &L, int e){
	DLNode *ptr = L;
	while(ptr->next)
		ptr = ptr->next;
	DLNode *r = NewDLNode(e);
	ptr->next = r;
	r->pred = ptr; 
}

void Print(DLinkedList L) {
	DLNode *ptr = L->next;
	printf("head<->");
	while(ptr){
		printf("%d(%d)<->", ptr->data, ptr->freq);
		ptr = ptr->next;
	}
	printf("NULL\n");
}

int main() {
	// 测试用例 
	DLinkedList L = NewDLNode(0); // 头结点
	
	// 插入节点
	InsertNode(L, 1);
	InsertNode(L, 2);
	InsertNode(L, 3);
	InsertNode(L, 4);
	InsertNode(L, 5);

	Print(L);

	Locate(L,3);
	Locate(L,2);
	Locate(L,2);

	Print(L);

    return 0;
}
